package com.mdnote.jianzhi_offer.array;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description 剑指 Offer 03. 数组中重复的数字
 */
public class Offer03I {


    public static void main(String[] args) {
        Offer03I offer03 = new Offer03I();
        int repeatNumber = offer03.findRepeatNumber(new int[]{1,2,3,4,0,1,2,1});
        System.out.println(repeatNumber);
    }
    /**
     * 解法：
     * 1. 哈希表 时间O(N) 空间 O(N)
     * 2. 交换法 （题目闲着了值的大小） 时间 O(N) 空间 (O1)
     */
    public int findRepeatNumber(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            while(i != nums[i]) {

                // 发现存在换来换去的现象
                if (nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                int tmp = nums[i]; nums[i] = nums[tmp]; nums[tmp] = tmp;

            }
        }
        return -1;
    }
}
